package com.asia.algorithmcode.binaryTree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @DESCRIPTION: 114、二叉树展开为链表
 * @USER: wanfu
 * @DATE: 2025/5/13 星期二 17:20
 */
public class Flatten {
    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        TreeNode t6 = new TreeNode(6);

        t1.left = t2;
        t2.left = t3;
        t2.right = t4;
        t1.right = t5;
        t5.right = t6;

        new Flatten().flatten(t1);

        System.out.println();
    }

    /**
     * 使用类似Morris遍历的方法解决,O(n)的时间，O(1)的空间,运行结果是100的时间；84.96的空间
     *
     * @param root
     */
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode p;
        while (root != null) {
            if (root.left == null) {
                root = root.right;
            } else {
                p = root.left;
                while (p.right != null) {
                    p = p.right;
                }
                p.right = root.right;
                root.right = root.left;
                root.left = null;
                root = root.right;
            }
        }
    }


    /**
     * 尝试使用O(1)的空间完成这个事情,此种方法实际空间不是O(1),但是也能通过，但是这里面已经有了morris遍历的味道
     *
     * @param root
     */
//    public void flatten(TreeNode root) {
//        if (root == null) {
//            return;
//        }
//        TreeNode left = root.left;
//        TreeNode right = root.right;
//        TreeNode rr = left;
//
//        if (rr != null) {
//            while (rr.right != null) {
//                rr = rr.right;
//            }
//            rr.right = right;
//            root.right = left;
//            root.left = null;
//        }
//        flatten(left);
//        flatten(right);
//    }

//
//    /**
//     * 先使用前序遍历拿到顺序，再将所有节点的左孩子置为空，右孩子指向下一个节点。（时间pass25）
//     * @param root
//     */
//    public void flatten(TreeNode root) {
//        if (root == null || (root.left == null && root.right == null)) {
//            return;
//        }
//        Deque<TreeNode> list = new LinkedList<>();
//
//        List<TreeNode> resList = new ArrayList<>();
//
//        while (root != null || !list.isEmpty()) {
//            while (root != null) {
//                resList.add(root);
//
//                list.push(root);
//                root = root.left;
//
//            }
//            TreeNode pop = list.pop();
//            root = pop.right;
//        }
//
//        int size = resList.size();
//        for (int i = 1; i < size; i++) {
//            resList.get(i - 1).left = null;
//            resList.get(i - 1).right = resList.get(i);
//        }
//    }

}
